package lineartable

import "errors"

/*
practice:
单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点
*/

// A singly linked list int node which value is int type.
type IntNode struct {
	Val  int
	Next *IntNode
}

// For each the linked node.
func ForEach(head *IntNode, callback func(val *IntNode)) {
	for node := head; node != nil; node = node.Next {
		callback(node)
	}
}

// TODO
// 求链表的中间结点
// 先遍历，总数/2 就是中间节点
func MiddleNode(head *IntNode) *IntNode {

	return nil
}

// TODO
// 删除链表倒数第 n 个结点
// 先遍历，总数-n 就是正数第几个节点
func DeleteNodeCountBackwards(head *IntNode, num int) {

}

// 两个有序的链表合并（假定从小到大的顺序）
func MergeLinkedList(head1 *IntNode, head2 *IntNode) (result *IntNode, err error) {
	if nil == head1 || nil == head2 {
		return result, errors.New("one of the linked list is empty")
	}

	var node1, node2 *IntNode
	if head1.Val <= head2.Val {
		result = head1
		node1 = head1.Next
		node2 = head2
	} else {
		result = head2
		node1 = head1
		node2 = head2.Next
	}

	for node := result; nil != node1 || nil != node2; {
		if nil != node1 && nil != node2 {
			if node1.Val <= node2.Val {
				node.Next = node1
				node1 = node1.Next
			} else {
				node.Next = node2
				node2 = node2.Next
			}
		} else if nil == node1 && nil != node2 {
			node.Next = node2
			node2 = node2.Next
		} else if nil == node2 && nil != node1 {
			node.Next = node1
			node1 = node1.Next
		} else if nil == node1 && nil == node2 {
			break
		}
		node = node.Next
	}

	return
}

// 链表中环的检测 O(n) O(n^2) O(n^2)
// nil
// pre
// pre->pre
// pre->cur->pre
// pre->cur->next->pre
// pre->cur->next->cur
func HasRing(head *IntNode) bool {
	if nil == head || nil == head.Next {
		return false
	}

	if head.Next == head {
		return true
	}

	// 单向链表，如果存在环，只会是最后一个元素的下一个元素是之前的某一个元素
	// 先得取最后一个元素
	for node := head; nil != node; node = node.Next {
		for compNode := head; nil != compNode && compNode != node; compNode = compNode.Next {
			if node.Next == compNode {
				return true
			}
		}
	}
	return false
}

// 单链表反转 O(n)
// nil
// pre
// pre->cur => pre<-cur
// pre->cur->next => pre<-cur<-next
// pre->cur->next->end => pre<-cur<-next<-end
func TraverseNodes(head *IntNode) (result *IntNode) {
	if nil == head {
		return nil
	}
	if nil == head.Next {
		result = head
		return
	}

	for node := head; node != nil; {
		tmp := node.Next
		if nil == result {
			node.Next = nil
			result = node
		} else {
			node.Next = result
			result = node
		}
		node = tmp
	}
	return
}
